/* ************************************
 * TreeGen
 * 
 * ************************************
 */
 
static final int NODE_HEIGHT = 55;
static final int NODE_WIDTH  = 30;

static final int GRAPH_NODE_WIDTH = 50;
static final int GRAPH_NODE_HEIGHT = 130;
static final int GRAPH_NODE_ACTUAL_HEIGHT = 50;
static final int INTER_NODE_OFFSET = 10;			// distance between adjacent leaf nodes in graph


// hash map for keeping names unique
HashMap<String, Boolean> unique_names = null;

float gaussian()
{
	float u1 = random(1.0);
	float u2 = random(1.0);
	
	float R = sqrt( -2.0 * log(u1) );
	return R * cos(2.0 * PI * u2);
}

int gaussianIntRange(float rangeMin, float rangeMax)
{
	// maximum of 3 standard deviations
	
	float g = min(3.0, abs(gaussian()));
	int x = round( (g / 3.0) * ( rangeMax - rangeMin ) + rangeMin );
	return x;
}

class NameException extends Exception
{
	NameException(String txt)
	{
		super(txt);
	}
}

class NameList
{
	ArrayList<String> names;
	ArrayList<String> letters;
	
	int curIndex;
	int curLetterIndex;
	
	NameList()
	{
		populate();
		reset();
	}
	
	void populate()
	{
		names = new ArrayList<String>();
		letters = new ArrayList<String>();
		
		// populate
		for (int i = 0; i < 26; i++)
		{
			char a = (char) (i + 'A');

			for (int j = 0; j < 26; j++)
			{
				char b = (char) (j + 'A');
				String n = "";
				n += a;
				n += b;
				
				names.add( n );
			}
			
			String letter = "";
			letter += a;
			letters.add( letter );
		}
	}	
	
	void reset()
	{
		
		// permuatate
		for (int i = 0; i < 10000; i++)
		{
			int i1 = int(random( names.size() ));
			int i2 = int(random( names.size() ));
			
			String temp = names.get(i1);
			names.set(i1, names.get(i2));
			names.set(i2, temp);
		}
		
		for (int i = 0; i < 1000; i++)
		{
			int i1 = int(random( letters.size() ));
			int i2 = int(random( letters.size() ));
			
			String temp = letters.get(i1);
			letters.set(i1, letters.get(i2));
			letters.set(i2, temp);
		}
		curIndex = 0;
		curLetterIndex = 0;
	}
	
	String getName() throws NameException
	{
		if (curIndex == names.size())
		{
			throw new NameException("No more random names.");
		}
		else
		{
			return names.get( curIndex++ );
		}
	}
	
	String getLetterName() throws NameException
	{
		if ( curLetterIndex == letters.size() )
		{
			throw new NameException("No more random names.");
		}
		else
		{
			return letters.get( curLetterIndex++ );
		}		
	}
}

// a class for name list
NameList name_list = new NameList();

class Node
{
	boolean locSet, widthSet;
	int nodeWidth;
	int x;
	int y;
	String txt;
	color fillColor;
	
	int maxChild, minChild, global_maxChild;
	int treeDepth;
	
	Node parent;
	ArrayList<Node> children;
	
	Node(Node _parent)
	{
		children = new ArrayList<Node>();
		locSet = false;
		widthSet = false;
		nodeWidth = x = y = 0;
		parent = _parent;
	
		// generate random string
		//newName();
		txt = null;		
	}
	
	void newName()
	{
		if (children.size() > 0) 
		{
			// get a single-letter name
			try
			{
				this.txt = name_list.getLetterName();
			}
			catch (Exception e) {
				this.txt = "?";
			}
		}
		else
		{
			// get a two-letter name
			try 
			{
				this.txt = name_list.getName();
			}
			catch (Exception e) {
				this.txt = "??";
			}
		}
	}
}

class TreeParameters
{
	int maxDepth;
	int rootMin, rootMax;
	int avgMin, avgMax;
	
	int maxFertileCount;
	int fertileMin, fertileMax;
	float fertilePercentage;
}

/* ------------------------------------------------------------------------- */

Node makeNewTree(int maxDepth)
{
	// clear out hash map
	unique_names = new HashMap<String, Boolean>();
	name_list.reset();
	
	print("generating tree...\t\t");
	
	// initialize parameters
	TreeParameters parameters = new TreeParameters();
/*
	parameters.maxDepth			= maxDepth;
	parameters.rootMin			= rootChildMin;
	parameters.rootMax			= rootChildMax;
	parameters.avgMin			= otherChildMin;
	parameters.avgMax			= otherChildMax;
*/

	// fertile branches (have more nodes under them)
	parameters.fertilePercentage		= 0.00;
	parameters.maxFertileCount		= 2;		// allow only one fertile branch
	parameters.fertileMin			= 3;
	parameters.fertileMax			= 3;


	// make the tree
	Node newTree = new Node(null);		// root
	generateTree( newTree, parameters, 0 );
	
	// layout
	layout( newTree );
	
	println("Done");
	
	return newTree;
}

void layout( Node tree)
{
	maxChild = -1;
	layoutIcicle( tree );
	layoutGraphNodes( tree, 0, 0 );
}

void generateTree( Node root, TreeParameters parameters, int curDepth)
{
	boolean depthExceeded = false;
	
	if (curDepth > parameters.maxDepth) {
		depthExceeded = true;
	}
	
	int childCount = 0;
	if (curDepth == 0)
	{
		//childCount = int(random( parameters.rootMax - parameters.rootMin + 1)) + parameters.rootMin;
		childCount = gaussianIntRange(parameters.rootMin, parameters.rootMax);
	}
	else if (!depthExceeded)
	{
		float p = random(1);
		if (p < parameters.fertilePercentage && (parameters.maxFertileCount == -1 || parameters.maxFertileCount > 0 ))
		{
			//childCount = int(random( parameters.fertileMax - parameters.fertileMin + 1)) + parameters.fertileMin;
			childCount = gaussianIntRange( parameters.fertileMin, parameters.fertileMax);
			if (parameters.maxFertileCount != -1)
			{
				// decrement allowable fertiles
				parameters.maxFertileCount--;
			}
		}
		else
		{
			//childCount = int(random( parameters.avgMax - parameters.avgMin + 1)) + parameters.avgMin;
			childCount = gaussianIntRange( parameters.avgMin, parameters.avgMax );
		}
	}
	
	// make children
	for (int i = 0; i < childCount; i++)
	{
		Node child = new Node( root );
		root.children.add( child );
		
		generateTree( child, parameters, curDepth + 1 );
	}
	
	root.newName();
}

int layoutIcicle( Node tree )
{
	if (tree.children.size() == 0)
	{
		tree.nodeWidth = 1;
	}
	else
	{
		tree.nodeWidth = 0;
		for (int i = 0; i < tree.children.size(); i++)
		{
			tree.nodeWidth += layoutIcicle( tree.children.get(i) );
		}
	}
	
	tree.widthSet = true;
	return tree.nodeWidth;
}

int layoutGraphNodes( Node tree, int xOffset, int yOffset )
{
	
	// render my children
	int x = 0;
	int averageChildX = 0;
	int local_minChild = MAX_INT;
	int local_maxChild = MIN_INT;
	
	for ( int i = 0; i < tree.children.size(); i++ )
	{
		
		Node child = tree.children.get( i );
		
		int cX = layoutGraphNodes( child, xOffset + (GRAPH_NODE_WIDTH + INTER_NODE_OFFSET) * x, GRAPH_NODE_HEIGHT + yOffset );
		
		x += child.nodeWidth;
		averageChildX += cX;
		
		local_minChild = min(local_minChild, cX);
		local_maxChild = max(local_maxChild, cX);
		
		maxChild = max(maxChild, local_maxChild);

	}

	if (tree.children.size() > 0)
	{
		tree.x = (local_minChild + local_maxChild) / 2;
		tree.fillColor = NONLEAF_COLOR;
		
		tree.maxChild = local_maxChild;
		tree.minChild = local_minChild;
	}
	else
	{
		tree.fillColor = LEAF_COLORS[ floor(random( LEAF_COLOR_COUNT )) ];
		tree.x = xOffset;
	}
	
	tree.y = yOffset;
	tree.locSet = true;

	return tree.x;
	
}

void renderIcicle( Node tree, HashMap<String, Boolean> hilight_map )
{
	boolean hilight = hilight_map.get( tree.txt ) != null;
	
	// render my self
	if (hilight)
	{
		fill(HILIGHT_COLOR);
	}
	rect( 0, 0, NODE_WIDTH * tree.nodeWidth, NODE_HEIGHT );
	
	// remove the fill
	fill(0);
	noFill();
	text( tree.txt, NODE_WIDTH * tree.nodeWidth / 2, NODE_HEIGHT / 2 );
	
	// render my children
	int x = 0;
	for ( int i = 0; i < tree.children.size(); i++ )
	{
		
		Node child = tree.children.get( i );
		pushMatrix();
		{
			translate( NODE_WIDTH * x, NODE_HEIGHT );
			renderIcicle( child, hilight_map );
			x += child.nodeWidth;
		}
		popMatrix();
	}
}

void renderGraph( Node tree, HashMap<String, Boolean> hilight_map )
{
	int x = tree.x;
	int y = tree.y;
	
	// see if this node to be highlighted
	boolean hilight = hilight_map.get( tree.txt ) != null;

		
	// render my self
	pushStyle();
	
	if (hilight)
	{
		fill(HILIGHT_COLOR);
	}
	else
	{
		fill( tree.fillColor );
	}
	
	rect( x + 5, y, GRAPH_NODE_WIDTH - 5 , GRAPH_NODE_ACTUAL_HEIGHT );
	fill(0);
	text( tree.txt, x + GRAPH_NODE_WIDTH / 2, y + GRAPH_NODE_ACTUAL_HEIGHT / 2 );

	popStyle();
	// draw children
	for ( int i = 0; i < tree.children.size(); i++ )
	{
		
		// get child
		Node child = tree.children.get( i );
		
		// draw link
		line( x + (GRAPH_NODE_WIDTH+10) / 2,1+ y + GRAPH_NODE_ACTUAL_HEIGHT, child.x + (GRAPH_NODE_WIDTH+10) / 2, child.y );

		// render child
		renderGraph( child, hilight_map );
	}	
}

String generateTabs( int len )
{
	String tab = "";
	for (int i = 0; i < len; i++)
	{
		tab += '\t';
	}
	return tab;
}

Node readTree( CachedFileReader input, Node parent, int curDepth )
{	
	// read node name
	String l = trim(input.readLine());
	if ( l.charAt(0) == '}' )
	{
		return null;
	}
	else if ( l.charAt( l.length() - 1 ) == '{' )
	{
		// new parent node
		Node newNode = new Node( parent );
		newNode.txt = trim(split( l, " " )[0]);
		
		while ( true )
		{
			Node childNode = readTree( input, newNode, curDepth + 1 );
			if (childNode == null)
			{
				break;
			}
			else
			{
				newNode.children.add( childNode );
			}
		}
		
		treeDepth = max(curDepth, treeDepth);
		return newNode;
	}
	else
	{
		// use text as node name
		Node newNode = new Node( parent );
		newNode.txt = l;
		
		treeDepth = max(curDepth, treeDepth);
		return newNode;
	}
}


























